<!DOCTYPE html>
<html xmlns="http://www.w3.org/1999/xhtml" lang="" xml:lang="">
  <head>
    <meta charset="utf-8" />
    <meta name="generator" content="pandoc" />
    <meta
      name="viewport"
      content="width=device-width, initial-scale=1.0, user-scalable=yes"
    />
    <title>README</title>
    <style type="text/css">
      code {
        white-space: pre-wrap;
      }
      span.smallcaps {
        font-variant: small-caps;
      }
      span.underline {
        text-decoration: underline;
      }
      div.column {
        display: inline-block;
        vertical-align: top;
        width: 50%;
      }
    </style>
  </head>
  <body>
    <h1 id="knuth-morris-pratt">Knuth-Morris-Pratt</h1>
    <p>
      The <strong>Knuth-Morris-Pratt</strong> algorithm is a string matching
      algorithm that searches for occurrences of a
      <strong>pattern string</strong> <code>P</code> within another string
      <code>S</code>. It does so by employing the observation that when a
      mismatch occurs, the word itself embodies sufficient information to
      determine where the next match could begin.
    </p>
    <h2 id="prefix-table">Prefix Table</h2>
    <p>
      KMP uses a pre-generated table called a <strong>prefix table</strong>. The
      prefix table allows us to skip certain comparisons.
    </p>
    <p>
      The values in the prefix table are the <strong>length</strong> of the
      longest proper <strong>prefix</strong> that maches a proper
      <strong>suffix</strong>.
    </p>
    <pre><code>A C A C A G T
0 0 1 2 3 0 0

A
AC
ACA
ACAC

A
CA
ACA
CACA</code></pre>
    <h2 id="terminology">Terminology</h2>
    <h4 id="proper-prefix">Proper prefix:</h4>
    <p>Characters in a string excluding one or more characters at the end.</p>
    <pre><code>string   = &#39;AYYYYY&#39;
prefixes = [&#39;A&#39;, &#39;AY&#39;, &#39;AYY&#39;, &#39;AYYY&#39;, &#39;AYYYY&#39;]</code></pre>
    <h4 id="proper-suffix">Proper suffix:</h4>
    <p>
      Characters in a string excluding one or more characters at the beginning.
    </p>
    <pre><code>string   = &#39;LMAOO&#39;
suffixes = [&#39;MAOO&#39;, &#39;AOO&#39;, &#39;OO&#39;, &#39;O&#39;]</code></pre>
    <h4 id="references"><em>References</em></h4>
    <p>
      <em
        ><a
          href="https://en.wikipedia.org/wiki/Knuth%E2%80%93Morris%E2%80%93Pratt_algorithm"
          >Wikipedia — Knuth–Morris–Pratt algorithm</a
        ></em
      >
    </p>
    <p><a href="#Knuth-Morris-Pratt">↑</a></p>
  </body>
</html>
